package leetcode101.bit_operation;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code6
 * @Description 318. 最大单词长度乘积
 * 给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，
 * 并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
 *
 * 示例 1:
 *
 * 输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
 * 输出: 16 
 * 解释: 这两个单词为 "abcw", "xtfn"。
 * 示例 2:
 *
 * 输入: ["a","ab","abc","d","cd","bcd","abcd"]
 * 输出: 4 
 * 解释: 这两个单词为 "ab", "cd"。
 * 示例 3:
 *
 * 输入: ["a","aa","aaa","aaaa"]
 * 输出: 0 
 * 解释: 不存在这样的两个单词。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-05 11:12
 */
public class Code6 {
    public static void main(String[] args) {
        String[] words = new String[]{"edadc","ebbfe","aacdde","dfe","cb","fddddff","fabca","adccac","ece","ccaf","feba","bcb","edadc","aea","bacb","acefa","fcebffd","dfeebca","bedcbaa","deaccc","abedc","dadff","eef","ddebbb","abecab","cd","abdeee","eedce","deef","dceaddd","ced","fbbf","ba","eefeda","fb","cddc","adafbf","dded","aadbf","caefbaf","ccebf","dbb","ee","dadcecc","ddbcabb","afeaa","ec","aad","efde","cbcda","cdbdafd","cddc","ecaaa","ae","cfc","bccac","cdcc","abbbf","fcdface","ddbcdc","bfebb","daed","bc","dc","ecdfc","eeb","bb","dad","caecb","fbe","bbbc","cacea","dbc","fbe","bcfffbd","aeda","cff","ddfc","ea","bdfd","ccb","cb","ae","ceabefa","dcea","cbaed","bfedf","fa","ccd","fece","bceef","acabca","dafa","fdeec","dac","cae","adeeadb","ecacc","acfe","de"};
        System.out.println(maxProduct(words));
    }

    public static int maxProduct(String[] words) {
        Map<String, Integer> words2Hex = new HashMap<>();
        int val, temp, max = 0;
        for (String word : words) {
            val = 0;
            for (int i = 0; i < word.length(); i++) {
                temp = 1 << word.charAt(i) - 'a';
                if (((val >> word.charAt(i) - 'a') & 1) != 1) {
                    val += temp;
                }
            }
            System.out.println(word + ": " + val);
            words2Hex.put(word, val);
            Iterator<Map.Entry<String, Integer>> iterator = words2Hex.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<String, Integer> entry = iterator.next();
                int v = entry.getValue();
                String k = entry.getKey();
                if ((v & val) == 0) {
                    max = Math.max(max, word.length() * k.length());
                }
//                if (max == word.length() * k.length()) System.out.println(k + ", " + word);
            }
        }
        return max;
    }

}
